package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/26
 * @description: 二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 */
public class B_144_二叉树的前序遍历 {


	/**
	 * 通过 递归进行前序遍历
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversalByRecursive(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		//进行先序遍历 - 根 左 右
		//res.add(root.val);
		preorder(root, res);
		return res;
	}

	private void preorder(TreeNode node, List<Integer> list) {
		list.add(node.val);
		if (node.left != null) {
			preorder(node.left, list);
		}
		if (node.right != null) {
			preorder(node.right, list);
		}
	}

	/**
	 * 通过迭代进行前序遍历
	 *
	 * @param root
	 * @return
	 */
	public static List<Integer> preorderTraversalByIterator(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		//通过一个栈维护之前未处理的右节点
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		while (cur.left != null || cur.right != null || !stack.isEmpty()) {
			res.add(cur.val);
			if (cur.left != null && cur.right != null) {
				//处理 根
				//res.add(cur.val);
				stack.push(cur);
				cur = cur.left;
			} else if (cur.left != null) {
				//left != null & right == null
				//res.add(cur.val);
				cur = cur.left;
			} else if (cur.right != null) {
				//left == null & right != null
				//res.add(cur.val);
				cur = cur.right;
			} else {
				//left == null & right == null
				//res.add(cur.val);
				cur = stack.pop().right;
			}
		}
		res.add(cur.val);
		return res;
	}

	/**
	 * 通过迭代进行先序遍历
	 * 无影响地自己的写法
	 *
	 * @param root
	 * @return
	 */
	public static List<Integer> preorderTraversalByIterator2(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		stack.push(cur);
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null) {
				//执行处理根节点 - 一直处理的是有左节点的根节点
				res.add(cur.val);
				if (cur.right != null) {
					stack.push(cur.right);
				}
				cur = cur.left;
			}
			//此时找到最左边的节点，可以直接处理 左节点
			res.add(cur.val);
			if (cur.right != null) {
				stack.push(cur.right);
			}
		}
		return res;
	}

	/**
	 * 对于 preorder 来说，readLeft 累赘了
	 * @param root
	 * @return
	 */
	public static List<Integer> preorderByIterator3(TreeNode root){
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(cur);
		boolean readLeft = false;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !readLeft) {
				res.add(cur.val);

				if (cur.right != null) {
					stack.push(cur.right);
				}
				cur = cur.left;
			}
			//leftest node
			res.add(cur.val);

			if (cur.right != null) {
				stack.push(cur.right);
				readLeft = false;
			}else {
				readLeft = true;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		testPreOrder();
		testPreOrder3();

//		TreeNode root = new TreeNode(1);
//		root.right = new TreeNode(2);
//		root.right.left = new TreeNode(3);
//		List<Integer> list = preorderTraversalByIterator(root);
//		System.out.println("list = " + list);


	}

	static void testPreOrder(){
		TreeNode node = TreeNode.stringToTreeNode("[1,null,2,3]");
		List<Integer> list = preorderTraversalByIterator2(node);
		System.out.println("list = " + list);
	}

	static void testPreOrder3(){
		TreeNode node = TreeNode.stringToTreeNode("[1,null,2,3]");
		List<Integer> list = preorderByIterator3(node);
		System.out.println("list = " + list);
	}


}
